1.1 Field of the Invention
The present invention relates to methods and apparatus for signal detection, classification, estimation, and processing. The invention is applicable to all types of “signals” and data, including but not limited to signals, images, video and other higher-dimensional data.
1.2 Brief Description of the Related Art
Compression of signals is a necessity in a wide variety of systems. In general, compression is possible because often we have considerable a priori information about the signals of interest. For example, many signals are known to have a sparse representation in some transform basis (Fourier, DCT, wavelets, etc.) and can be expressed or approximated using a linear combination of only a small set of basis vectors.
The traditional approach to compressing a sparse signal is to compute its transform coefficients and then store or transmit the few large coefficients along with their locations. This is an inherently wasteful process (in terms of both sampling rate and computational complexity), since it forces the sensor to acquire and process the entire signal even though an exact representation is not ultimately required. In response, a new framework for simultaneous sensing and compression has developed recently under the rubric of Compressed Sensing (CS). CS enables a potentially large reduction in the sampling and computation costs at a sensor, specifically, a signal having a sparse representation in some basis can be reconstructed from a small set of nonadaptive, linear measurements (see E. Candès, J. Romberg, and T. Tao, “Robust uncertainty principles: Exact signal reconstruction from highly incomplete frequency information”, IEEE Trans. Information Theory, Submitted, 2004 and D. Donoho, “Compressed sensing”, IEEE Trans. Information Theory, Submitted, 2004). Briefly, this is accomplished by generalizing the notion of a measurement or sample to mean computing a linear function of the data. This measurement process can be represented in terms of matrix multiplication. In E. Candès, J. Romberg, and T. Tao, “Robust uncertainty principles: Exact signal reconstruction from highly incomplete frequency information”, IEEE Trans. Information Theory, Submitted, 2004 and D. Donoho, “Compressed sensing”, IEEE Trans. Information Theory, Submitted, 2004 conditions upon this matrix are given that are sufficient to ensure that we can stably recover the original signal using a tractable algorithm. Interestingly, it can be shown that with high probability, a matrix drawn at random will meet these conditions.
CS has many promising applications in signal acquisition, compression, medical imaging, and sensor networks; the random nature of the measurement matrices makes it a particularly intriguing universal measurement scheme for settings in which the basis in which the signal is sparse is unknown by the encoder or multi-signal settings in which distributed, collaborative compression can be difficult to coordinate across multiple sensors. This has inspired much interest in developing real-time systems that implement the kind of random measurement techniques prescribed by the CS theory. Along with these measurement systems, a variety of reconstruction algorithms have been proposed (see E. Candès, J. Romberg, and T. Tao, “Robust uncertainty principles: Exact signal reconstruction from highly incomplete frequency information”, IEEE Trans. Information Theory, Submitted, 2004, D. Donoho, “Compressed sensing”, IEEE Trans. Information Theory, Submitted, 2004, and J. Tropp and A. C. Gilbert, “Signal recovery from partial information via orthogonal matching pursuit”, Preprint, April 2005), all of which involve some kind of iterative optimization procedure, and thus are computationally expensive for long signals with complexity typically polynomial in the signal length.
1.2.1 Compressed Sensing Background
Let x∈N be a signal and let the matrix Ψ:=[ψ1, ψ2, . . . , ψZ] have columns that form a dictionary of vectors in N. (This dictionary could be a basis or a redundant frame.) When we say that x is K-sparse, we mean that it is well approximated by a linear combination of K vectors from Ψ; that is, x≈Σi=1Kαniψni with K<<N.
1.2.2 Incoherent Measurements
Consider a signal x that is K-sparse in Ψ. Consider also an M×N measurement matrix Φ, M<<N, where the rows of Φ are incoherent with the columns of Ψ. For example, let Φ contain i.i.d. Gaussian entries; such a matrix is incoherent with any fixed Ψ with high probability (universality). Compute the measurements y=Φx and note that y∈M with M<<N. The CS theory in E. Candès, J. Romberg, and T. Tao, “Robust uncertainty principles: Exact signal reconstruction from highly incomplete frequency information”, IEEE Trans. Information Theory, Submitted, 2004 and D. Donoho, “Compressed sensing”, IEEE Trans. Information Theory, Submitted, 2004 states that there exists an overmeasuring factor c>1 such that only M:=cK incoherent measurements y are required to reconstruct x with high probability. That is, just cK incoherent measurements encode all of the salient information in the K-sparse signal x.
1.2.3 Reconstruction from Incoherent Projections
The amount of overmeasuring required depends on the (nonlinear) reconstruction algorithm. Most of the existing literature on CS has concentrated on optimization-based methods for signal recovery, in particular l1 minimization. The l1 approach seeks a set of sparse coefficients {circumflex over (α)} by solving the linear program in S. Chen, D. Donoho, and M. Saunders, “Atomic decomposition by basis pursuit”, SIAM Journal on Scientific Computing, Vol. 20, No. 1, Pages 33-61, 1998
            α      ^        =                  arg        ⁢                                  ⁢                              min            α                    ⁢                                                                    α                                            1                        ⁢                                                  ⁢            subject            ⁢                                                  ⁢            to            ⁢                                                  ⁢            Θ            ⁢                                                  ⁢            α                              =      y        ,where Θ=ΦΨ is the holographic basis. Greedy reconstruction algorithms build up a signal approximation iteratively by making locally optimal decisions. A particularly simple approach is that of Matching Pursuit (MP). As described in S. Mallat and Z. Zhang, “Matching pursuits with time-frequency dictionaries”, IEEE Trans. Signal Processing, Vol. 41, No. 12, 1993, MP is an efficient greedy algorithm that selects basis vectors one-by-one from a dictionary to optimize the signal approximation at each step. In its application to CS, MP seeks a sparse representation of the measurement vector y in the dictionary {θi} consisting of column vectors from the holographic basis Θ. In order to describe MP, we introduce the notation
      〈          x      ,      y        〉    ⁢      :    =            ∑              i        =        1            N        ⁢                  x        i            ⁢              y        i            where xi and yi denote the i-th entries of the length-N vectors x and y.